DAG Covers
September 25, 2026 (1pm, GHC 4405 - part of the Theory Seminar series)

I will give a survey-style talk about the recently defined notion of a "DAG cover". It is a directed analog of a tree cover, which is closely related to a probabilistic tree embedding. A DAG cover of a general directed graph G is a small collection of DAGs so that for all pairs of vertices s,t in G, some DAG in the collection provides low distortion for dist(s,t). This talk will discuss the known results on DAG covers and its variants, with a focus on posing open problems.